class Solution {
    /**
     * d[1] = 1*1+d[0]
     * d[2] = 1*1+d[1]
     * d[3] = 1*1+d[2]
     * d[4] = 1*1+d[3], 2*2+d[0]
     * d[5] = 1*1+d[4], 2*2+d[1]
     */
    public int numSquares(int n) {
        int[] d = new int[n + 1];
        Arrays.fill(d, 5000);
        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                d[i] = Math.min(d[i], 1 + d[i - j * j]);
            }
        }
        return d[n];
    }
}